\section{Binomial Tree}\label{sec:binom}
A commonly used approach to compute the price of an option is the so-called
binomial tree method. In this model it is assumed that the price of a stock
can only go up or it can go down at each interval. Suppose that the maturity
of an option on a non-dividend-paying stock is divided into $N$ subintervals
of length $\delta t$. We will refer to the $i-th$ node at time $j\,\delta t$ as
the node $(i, j)$.

The stock price at the $(i, j)$ node is equal to
$S_{i,j}=S_0u^{j-i}d^{i-1}$. With $u$ and $d$ the upward and downward stock
price movements respectively, these are calculated in the following way:
\[
u = e^{\sigma\sqrt{\delta t}},\, d = e^{-\sigma\sqrt{\delta t}}\\
\]  
where $\sigma$ is the volatility of the stock.

In the binomial tree approach, option prices are computed through a backward
recursion scheme. This scheme is based on the risk-neutral valuation. In a
risk-neutral world all individuals are indifferent to risk. It doesn't matter
if the price of the stock goes up or down, the portfolio is worth the same. In
such a world the probability of an up movement along the tree is 
\[
p=\frac{e^{r\delta t}-d}{u-d}
\]
with $r$ the risk-free interest rate and $u$ and $d$ as defined before. The
value of an option in a risk-neutral world is its expected payoff in a
risk-neutral world discounted at the risk-free rate.

\subsection{European option}
First the binomial tree model will be used to value an European option. This
because this type of option is the easiest to price and it will give insights
on how to price American options. The payoff of an European call option at
expiry is $\max(0,S_{i,N} - K)$, with $K$ the strike price of the option and
$S_{i, N}$ the price of the underlying stock at node $i$ in the end layer $N$.
Risk-neutral valuation of the option gives:
\begin{eqnarray}\label{eq:optionprice}
f_{i,j}=e^{-r\delta t}(pf_{i,j+1}+(1-p)f_{i+1,j+1})
\end{eqnarray}
with $f_{i,j}$ the price of the option at $(j-1)\, \delta t$.
An example of a stock price and the price of an European call option on the
same non-dividend-paying stock with a maturity of one year (divided in 4
steps), a strike price of \euro 99.00, a one-year interest rate of 6\%, a
volatility of 20\%, and a current price of \euro 100.00 is given in figure
\ref{fig:callbinom}.

\begin{figure*}[h]
\caption{A Binomial tree of 4-layers for a Call option}\label{fig:callbinom}
\bigskip
\begin{center}
\renewcommand{\mynode}[2]{\begin{minipage}{1.2cm}\begin{center}{\footnotesize #1}%
	{\\[-2mm]\scriptsize \it #2} \end{center}\end{minipage}}
\begin{psmatrix}[rowsep=0.15cm,nodesep=2.9cm,colsep=3cm]
   &&&\mynode{35.9859}{134.9859}\\
	&&\mynode{24.6142}{122.1403}&\\
	&\mynode{16.1131}{110.5171}&&\mynode{11.5171}{110.5171}\\
\mynode{10.2373}{100.0000}&&\mynode{6.2453}{100.0000}&\\
	&\mynode{2.7985}{90.4837}&&\mynode{0.0000}{90.4837}\\
	&&\mynode{0.0000}{81.8731}&\\
	&&&\mynode{0.0000}{74.0818}
\ncline{4,1}{3,2} \ncline{4,1}{5,2}
\ncline{3,2}{2,3} \ncline{3,2}{4,3}
\ncline{5,2}{4,3} \ncline{5,2}{6,3}
\ncline{2,3}{1,4} \ncline{2,3}{3,4}
\ncline{6,3}{7,4} \ncline{6,3}{5,4}
\ncline{4,3}{3,4} \ncline{4,3}{5,4}
\end{psmatrix}
\medskip
\begin{minipage}{10cm}
{\footnotesize
The option price is computed using four layers. The strike price of the option
is \euro 99 the initial stock price is \euro 100 the volatility and interest
rate are respectively 20\% and 6\%. The price at the top of each node is the
value of the option. The price at the bottom of each node is the stock price
at that certain node.}
\end{minipage}
\end{center}
\end{figure*}


\subsubsection{Derivation Black Scholes}
Since the binomial tree proposed in the last sub section only assumes one
upwards or downwards movement it is not very realistic. To that end we derive
the Black-Scholes formula. This formula will permit to value an option using
an analytical approach.  The first step towards the Black-Scholes formula is
to change from discrete time to continuous time. To this end we need a
stochastic process, this because it is uncertain how the underlying stock will
behave. A stochastic process which is used to describe the stock price process
is the Brownian Motion, $W_t$. The Brownian motion has the following
properties:
\begin{itemize}
\item  $W_0=0$
\item $W_{n+t}-W_{n} \sim N(0,t)\,\forall n,t\geq0$
\item $W_{n+t}-W_n$ is stochastically independent of $W_u, \, u\leq W_n$
\item any sample path $t \rightarrow W_t(\omega)$ is a continuous function.
\end{itemize} 
An asset price process could be postulated to satisfy, for given stochastic
processes $\mu$ and $\sigma$, the drift and volatility of the process
respectively, 
\begin{equation}\label{eq:stocksde}
dS_t=\mu S  dt +\sigma S dW_t.
\end{equation}
This is a stochastic differential equation (SDE).

The quadratic variation of the stock price is the process $[S]$ such that
$d[S]_t=\sigma_t^2 dt$. By Ito's formula a transformation $f(S_t)$ of a
process that is a stochastic differential equation by a twice continuously
differentiable function $f$ again satisfies an stochastic differential
equation and is of the form
\[
df(S_t)=f'(S_t)dS_t+\frac{1}{2}f''(S_t)d[S]_t.
\]
If we suppose that a stock price evolves according to the stochastic process
\begin{equation}\label{eq:sde}
dS_t= rS dt + \sigma S dW_t
\end{equation}
with $W_t$ a Brownian Motion, then by Ito's
formula we can derive the stochastic differential equation from $\log S$.\\
\begin{eqnarray*}
d\log S&=&(r-\frac{1}{2})\sigma^2 dt+\sigma dW_t\\
\log S_T-\log S_0&=&(r-\frac{1}{2})\sigma^2 dt+\sigma dW_t\\
\end{eqnarray*}
This can be rewritten in the following way.
\begin{equation}\label{eq:direct}
S_t=S_0e^{(r-\frac{1}{2})\sigma^2t+\sigma W_t}
\end{equation}
We say that when a stock price can be written in this way, it is a geometric
Brownian Motion. From now on we assume that the stock price evolves according
to a Geometric Brownian Motion. Which is essential since if the stock price
would be modelled with a normal Brownian Motion the stock price could become
negative.

For simplicity we call $B_t = e^{rt}$. From this we can construct the value of
an portfolio at each time $t$, we call this 
\[
V_t= \phi S_t+ \psi_t B_t
\]
with $\phi_t$ the number of underlying assets, and $\psi_t$ the number of
bonds at $t$.  This portfolio is self-financing if $dV_t =
\phi_tdS_t+\psi_tdB_t$. A hedging portfolio is a self-financing portfolio
which satisfies $V_T=C$, with $C$ the
price of an option. In order to obtain such a portfolio the asset price has to
be discounted:
\[
\tilde S_t =e^{-rt}S_t=S_0e^{(\mu-r)t+\sigma W_t},
\]
By Ito's formula:
\[
d\tilde S_t = (\mu-r+\frac{1}{2}\sigma^2)\tilde S_t dt +\sigma \tilde S_tdW_t.
\]

If we define $\tilde W_t = W_t+t(\mu-r+\frac{1}{2}\sigma^2)/\sigma$ then
$d\tilde S_t = \sigma \tilde S_td\tilde W_t$. We can prove there is a process
$\tilde\phi$ such that $d\tilde V_t=\tilde\phi_td\tilde W_t$, but now we
assume this is true. If we now define $\phi_t=\tilde \phi_t/\sigma \tilde S_t$
and $\psi_t=\tilde V_t-\phi_t\tilde S_t$, then the portfolio consisting of
$(\phi,\psi)$ is a hedging portfolio for the derivative $C$ (by construction
$V_t=e^{rt}\tilde V_t =\mathbb{E}(C)=C$, and it is self-financing because by
Ito's lemma: $dV_t=\phi_t dS_t+\psi tdB_t$).

With some substitutions it follows that $d\tilde S_t =
e^{-rt}dS_t+S_tde^{-rt}\Rightarrow dS_t=rS_tdt+\sigma S_td\tilde W_t$. By
Ito's lemma $S_t=S_0e^{(r-\frac{1}{2}\sigma^2)t+\sigma \tilde W_t}$. So
under the risk neutral evaluation the stock price $S$ is also a Brownian motion
with drift $r-\sigma^2/2$ and volatility $\sigma$.

Due to the second property of the Brownian motion, this geometric Brownian
motion is equal to $S_t=S_0e^{(r-\frac{1}{2}\sigma^2)t+\sigma\sqrt{t}Z}$, with
$Z\sim N(0,1)$.\\
If the option is European, such that $f(S_T)=\max(0,S_T-K)$ then due to the
non-arbitrage argument the price for the option is equal to 
\begin{eqnarray*}
\mathbb{E}e^{-rT}f(S_T) &=& e^{-rt}\mathbb E f(S_0e^{(r-\frac{1}{2}\sigma^2)T+\sigma\sqrt{T}Z})\\
&=&\frac{e^{-rT}}{\sqrt{2\pi}}\int_{\mathbb R}f(S_0e^{(r-\frac{1}{2}\sigma^2)T+\sigma\sqrt{T}Z})e^{-\frac{1}{2}z^2}dz.\\
&=&S_0\Phi(d_1)-Ke^{-rT}\Phi(d_2)\\
\end{eqnarray*}
with
\[
d_1 =\frac{log(S_0/K)+(r+\sigma^2/2)T}{\sigma\sqrt T}, \, d_2=d_1-\sigma\sqrt T.
\]
this is the Black-Scholes formula.

\subsubsection{Comparison and Convergence of the Black Scholes and Binomial Tree}
The option price of an European option computed using a Binomial tree
converges to the price computed using the Black-Scholes formula. In figure
\ref{fig:callest}  and \ref{fig:putest} we can see that the error converges
faster to zero when approximating the price of a put option than when
approximating a call option.  The jig-saw behaviour of the approximation using
the Binomial tree is caused by the design of the tree and the computation of
the values at the node of each leaf. As can be deduced from the figures, the
error converges to zero which means that the jig-saw effect can be neglected
when using a high number of layers in the tree. However, as we will discuss in
the next sub section, using a Binomial tree for the approximation of an option
price is computationally expensive.

\begin{figure*}[h]
\caption{Option price estimations}
\begin{center}
\subfloat[Call option price estimation]{\label{fig:callest}%
	\includegraphics[width=7cm]{call_option_estimation}}\qquad
\subfloat[Put option price estimation]{\label{fig:putest}%
	\includegraphics[width=7cm]{put_option_estimation}}\\
\medskip
\begin{minipage}{14cm}
{\footnotesize The figures show the estimation of a put and call price using a
binomial tree compared to the analytical result. It is clear that the
approximation found using a binomial tree converges asymptotically to the
price found using the analytical Black-Scholes formula. Furthermore, both
approximations follow a jig-saw pattern. This is attributed to the property
of a binomial tree. Whenever a new layer is added the approximation will be
too high, or too low and thereby create the pattern.
\ref{fig:callbinom}.
}
\end{minipage}
\end{center}
\end{figure*}

\subsubsection{Computational Complexity}
The computational complexity of the underlying stock tree is $O(N^2)$, with
$N$ the amount of subintervals. This is derived in the following way.
In a one-step binomial tree, a $2\times2$-matrix, there are only two calculations
needed. The calculations are only on the final nodes. In a two-step binomial
tree, a $3\times3$-matrix, five calculations are necessary. So the number of
calculations for an $(N+1)\times(N+1)$-matrix is equal to
\[
\sum_{i=1}^{N+1}i=\frac{1}{2}(3N+N^2)=O(N^2)
\]
The computational complexity of an option tree is still $O(N^2)$, there are
exactly twice as much computations needed for a $(N+1)\times(N+1)$-matrix. First
the values of the underlying stock have to be calculated, and with these
values the values of the option can be calculated. So the total amount of
calculations is equal to $3N+N^2=O(N^2)$.  

\subsubsection{European Put Option}
In almost the same way as earlier for the European call option the payoff can
be calculated for the European put option. The only difference is that the
price at expiry date for the European put option is $\max(K-S_{i,N},0)$. An
example of a European put option on the same non-dividend-paying stock as
earlier is given in figure \ref{fig:putbinom}.

\begin{figure*}
\caption{A Binomial tree of 4-layers for a Put option}\label{fig:putbinom}
\bigskip
\begin{center}
\renewcommand{\mynode}[2]{\begin{minipage}{1.2cm}\begin{center}{\footnotesize #1}%
	{\\[-2mm]\scriptsize \it #2} \end{center}\end{minipage}}
\begin{psmatrix}[rowsep=0.15cm,nodesep=2.9cm,colsep=3cm]
   &&&\mynode{0.0000}{134.9859}\\
	&&\mynode{0.0000}{122.1403}&\\
	&\mynode{1.6702}{110.5171}&&\mynode{0.0000}{110.5171}\\
\mynode{4.8811}{100.0000}&&\mynode{3.7714}{100.0000}&\\
	&\mynode{8.9770}{90.4837}&&\mynode{8.5163}{90.4837}\\
	&&\mynode{15.6530}{81.8731}&\\
	&&&\mynode{24.9182}{74.0818}
\ncline{4,1}{3,2} \ncline{4,1}{5,2}
\ncline{3,2}{2,3} \ncline{3,2}{4,3}
\ncline{5,2}{4,3} \ncline{5,2}{6,3}
\ncline{2,3}{1,4} \ncline{2,3}{3,4}
\ncline{6,3}{7,4} \ncline{6,3}{5,4}
\ncline{4,3}{3,4} \ncline{4,3}{5,4}
\end{psmatrix}
\medskip
\begin{minipage}{10cm}
{\footnotesize The option parameters are the same as in figure
\ref{fig:callbinom}.
}
\end{minipage}
\end{center}
\end{figure*}
 
\subsubsection{Put-Call parity}
Denote $C_t$ and $P_t$ the prices at $t$ of an European call and put
option respectively. Both options have the same maturity $T$, and strike price
$K$. Assume that the risk-free interest rate is $r$ and we have an arbitrage
free market. Suppose two portfolios:
\begin{itemize}
\item Portfolio A: one European call option and an amount of cash equal to $Ke^{-rT}$
\item Portfolio B: one European put option and one share
\end{itemize}
Both these portfolios are worth $\max(S_T,K)$ at expiration date, with $S_T$
the price of the underlying stock at $T$. Due to the no-arbitrage argument the
values of the portfolio's must be equal $\forall t\in[0,T]$. Resulting in
\[
C_t + K e^{-r(T-t)} = P_t + S_t.
\]

\subsubsection{Delta Hedge}
\begin{figure*}
\caption{A Binomial tree of 4-layers for a Delta Hedge for an European Call
option.}\label{fig:delta}
\bigskip
\begin{center}
\renewcommand{\mynode}[1]{\begin{minipage}{1.2cm}\begin{center}{\footnotesize
#1}\end{center}\end{minipage}}
\begin{psmatrix}[rowsep=0.15cm,nodesep=2.9cm,colsep=3cm]
   &&&\mynode{0.0000}\\
	&&\mynode{1.0000}&\\
	&\mynode{0.8297}&&\mynode{0.0000}\\
\mynode{0.6353}&&\mynode{0.5749}&\\
	&\mynode{0.3445}&&\mynode{0.0000}\\
	&&\mynode{0.0000}&\\
	&&&\mynode{0.0000}
\ncline{4,1}{3,2} \ncline{4,1}{5,2}
\ncline{3,2}{2,3} \ncline{3,2}{4,3}
\ncline{5,2}{4,3} \ncline{5,2}{6,3}
\ncline{2,3}{1,4} \ncline{2,3}{3,4}
\ncline{6,3}{7,4} \ncline{6,3}{5,4}
\ncline{4,3}{3,4} \ncline{4,3}{5,4}
\end{psmatrix}
\medskip
\begin{minipage}{10cm}
{\footnotesize
This tree represents the delta hedge ratio for a European call option which
tree and specifications are given in figure \ref{fig:callbinom}.}
\end{minipage}
\end{center}
\end{figure*}

The delta of the stock option is the ratio of the change in the price of the
stock option to the change in the price of the underlying stock. It is the
number of units of the stock we should hold for each option sorted in order
to create a risk-less hedge.
\[
\Delta = \frac{\Delta f}{\Delta S}
\]
For a binomial tree the delta hedge at each node can be calculated by
dividing the change in option price by the change in stock price. The result
is the tree in figure \ref{fig:delta}.

The delta hedge for the analytical values is a bit more complicated. To
calculate the analytical delta hedge for an European call option first recall
the Black-Scholes formula.
\[
V_c(S_0)=S_0\Phi(d_1)-Ke^{-rt}\Phi(d_2)
\]
with $d_1=\frac{log(\frac{S_0}{K})+(r+\frac{\sigma^2}{2})T}{\sigma\sqrt T}, \,
d_2=d_1-\sigma\sqrt T$. The delta hedge is $\delta=\frac{\delta V(S_0)}{\delta
S_0}$ so\\
\begin{eqnarray*}
\delta&=&\Phi(d_1)+S_0 \frac{\delta \Phi}{\delta d_1}(d_1)\frac{\delta d_1}{\delta S_0}-Ke^{-rt}\frac{\delta \Phi}{\delta d_2}(d_2)\frac{\delta d_2}{\delta S_0}\\
&=&\Phi(d_1)+\frac{\delta d_1}{\delta S_0}(S_0 \frac{\delta \Phi}{\delta d_1}(d_1)-Ke^{-rt}\frac{\delta \Phi}{\delta d_2}(d_2)).
\end{eqnarray*}
Note that $\frac{\delta d_2}{\delta S_0}= \frac{\delta d_1}{\delta S_0}$. We
want to show that $S_0 \frac{\delta \Phi}{\delta
d_1}(d_1)=Ke^{-rt}\frac{\delta \Phi}{\delta d_2}(d_2)$, for this we are going
to use that $\frac{\delta \Phi}{\delta
d_1}=\frac{1}{\sqrt{2\pi}}e^{-\frac{d_1^2}{2}}$.
\begin{eqnarray*}
S_0 \frac{1}{\sqrt{2\pi}}e^{-\frac{d_1^2}{2}} &=&Ke^{-rT} \frac{1}{\sqrt{2\pi}}e^{-\frac{d_2^2}{2}}\\
S_0e^{-\frac{d_1^2}{2}} &=&Ke^{-rT}e^{-\frac{1}{2}(d_1-\sigma \sqrt T)^2}\\
S_0e^{-\frac{d_1^2}{2}} &=&Ke^{-rT}e^{\frac{-d_1^2}{2}}e^{d_1\sigma\sqrt T}e^{\frac{-\sigma^2 T}{2}}\\
S_0&=&e^{-rT}e^{\log(\frac{S_0}{K})+(r+\frac{\sigma^2}{2})T}e^{\frac{-\sigma^2T}{2}}\\
S_0&=&S_0\\
\end{eqnarray*}
Because of this equality $\delta = \Phi(d_1)$.

To calculate at the delta hedge for an European put option we fist need to
look at the Black-Scholes formula for a put option.
\begin{eqnarray*}
V_p(S_0)&=&Ke^{-rT}\Phi(-d_2)-S_0\Phi(-d_1)\\
&=&Ke^{-rT}(1-\Phi(d_2))-S_0(1-\Phi(d_1))\\
&=&Ke^{-rT}-S_0+V_c(S_0)\\
\end{eqnarray*}
with $V_c(S_0)$ the analytical value of the European call option. 
\begin{eqnarray*}
\frac{\delta V_p(S_0)}{\delta S_0}&=&-1+\frac{\delta V_c(S_0)}{\delta S_0}\\
&=&-1+\Phi (d_1)
\end{eqnarray*}

The Delta Hedge can also be computed using a Binomial tree. The hedge
parameter is than defined as $\delta = (V_{i + 1, j + 1} - V_{i, j + 1}) / (S_{i, j + 1} -
S_{i + 1, j + 1})$ where $V_{i, j}$ is the value of the option as defined in
sub section \ref{sec:binom}. In figure \ref{fig:deltaput} the value of the delta
computed using the analytic result is compared to the value found using a
binomial tree. It is clear from the figure that the binomial tree converges to
a value which is slightly different from the analytic result. However the
difference is so small that the error could be caused by floating point
arithmetic. 

\begin{figure*}
\caption{The Delta Hedge parameter for a put option}\label{fig:deltaput}
\begin{center}
	\includegraphics[width=\textwidth]{delta_put}
\begin{minipage}{14cm}
{\footnotesize From the graph can be concluded that the binomial approximation
never converges to the analytic result. The jig-saw pattern is similar to the
ones in figure \ref{fig:callest} and \ref{fig:putest}. The parameters of the put option are
equal to the ones in figure \ref{fig:callbinom}.
}
\end{minipage}
\end{center}
\end{figure*}

\subsection{American Option}
\begin{figure*}
\caption{A Binomial tree of 4-layers for an American Put option}%
	\label{fig:acallbinom}
\bigskip
\begin{center}
\renewcommand{\mynode}[2]{\begin{minipage}{1.2cm}\begin{center}{\footnotesize #1}%
	{\\[-2mm]\scriptsize \it #2} \end{center}\end{minipage}}
\begin{psmatrix}[rowsep=0.15cm,nodesep=2.9cm,colsep=3cm]
   &&&\mynode{0.0000}{134.9859}\\
	&&\mynode{0.0000}{122.1403}&\\
	&\mynode{1.6702}{110.5171}&&\mynode{0.0000}{110.5171}\\
\mynode{5.1701}{100.0000}&&\mynode{3.7714}{100.0000}&\\
	&\mynode{9.6297}{90.4837}&&\mynode{8.5163}{90.4837}\\
	&&\mynode{17.1269}{81.8731}&\\
	&&&\mynode{24.9182}{74.0818}
\ncline{4,1}{3,2} \ncline{4,1}{5,2}
\ncline{3,2}{2,3} \ncline{3,2}{4,3}
\ncline{5,2}{4,3} \ncline{5,2}{6,3}
\ncline{2,3}{1,4} \ncline{2,3}{3,4}
\ncline{6,3}{7,4} \ncline{6,3}{5,4}
\ncline{4,3}{3,4} \ncline{4,3}{5,4}
\end{psmatrix}
\medskip
\begin{minipage}{10cm}
{\footnotesize
The option parameters are the same as in figure
\ref{fig:callbinom}, except the fact that this is an American option which may
be exercised before maturity.}
\end{minipage}
\end{center}
\end{figure*}

Now suppose we have to value an American Option using a binomial tree. This
has to be done again with backwards recursion. The values at the final nodes
are the same as for the European option. At the earlier nodes the value of the
option is the greater of:
\begin{enumerate}
 \item The value given by equation \eqref{eq:optionprice},
 \item The payoff from early exercise.
\end{enumerate}
An example of a tree for an American call option is displayed in figure
\ref{fig:acallbinom}. When comparing the tree found when approximating the
value of European option to an American option we found that early exercise is
often optimal for a put option. This in contrast to a call option, where early
exercise is never advantageous.

Because of the right to have early exercise a American option is worth at
least as much as the corresponding European option. A call option, European or
American, always satisfies the following inequality $C_t\geq S_t-Ke^{r(T-t)}$,
so early exercise is never optimal. Some intuitive reasons for not doing early
exercise are the following: no income is sacrificed (because all the time we
assume a non-dividend paying stock), we delay paying the strike price (which
is better because then the value of the money has dropped), and holding the
call provides insurance against stock price falling below strike price.

While for a put option the European option always satisfies the following
inequality $P_t\geq Ke^{-r(T-t)}-S_t$, and the American option satisfies
$P_t\geq K-S_t$ which is obtained as soon as  the price of the stock option
falls sufficiently below the exercise price.


% vim: spell spelllang=en:autoindent:ft=tex
